#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
using namespace std;

class Solution {
public:
    void mergefind(vector<int>& nums, int begin, int end, int& ret, vector<int>& tmp)
    {
        if (begin >= end) return;
        int mid = (begin + end) / 2;
        mergefind(nums, begin, mid, ret, tmp);
        mergefind(nums, mid + 1, end, ret, tmp);
        int cur1 = begin, cur2 = mid + 1;
        int i = begin;
        while (cur1 <= mid && cur2 <= end)
        {
            if (nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
            else { tmp[i++] = nums[cur2++]; ret += mid - cur1 + 1; }
        }
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= end) tmp[i++] = nums[cur2++];
        for (int j = begin; j <= end; ++j)
            nums[j] = tmp[j];
    }

    int reversePairs(vector<int>& record) {
        int ret = 0;
        vector<int> tmp(record.size());
        mergefind(record, 0, record.size() - 1, ret, tmp);
        return ret;
    }
};